P3211 [HNOI2011]XOR和路径

异或的期望不能直接算，对每一位单独考虑。

$f[u][0/1]$:节点 $u$ 的第 $i$ 位为 $0/1$ 的概率。

注意经过节点 $u$ 的概率不一定为 $1$ ，所以 $f[u][0]+f[u][1]$ 的值不一定为 $1$。

$f[1][0]=1,f[1][1]=0$

$f_{u,0} = \begin{cases} \frac{f_{v,1}}{\deg_v} & \text{w第i位为1} \\ \frac{f_{v,0}}{\deg_v} & \text{w第i位为0} \end{cases}$

$f_{u,1}$ 同理。

高斯消元得到 $f_{n,1}$ , 乘上该位所对应的数即为该位的期望。对所有位求和即为答案。

时间复杂度 $\mathcal O(n^3\log w)$。

注意重边和自环的处理。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-8

const int MAXN = 200 , LOG = 31;

int w; double a[ MAXN + 5 ][ MAXN + 5 ];
void Gauss( ) {
	for( int i = 1 ; i <= w ; i ++ ) {
		int pos = i;
		for( int j = i + 1 ; j <= w ; j ++ )
			if( fabs( a[ pos ][ i ] ) < fabs( a[ j ][ i ] ) ) pos = j;
		swap( a[ i ] , a[ pos ] );
		if( fabs( a[ i ][ i ] ) < eps ) continue;
		for( int j = 1 ; j <= w ; j ++ )
			if( i != j ) {
				double del = a[ j ][ i ] / a[ i ][ i ];
				for( int k = 1 ; k <= w + 1 ; k ++ )
					a[ j ][ k ] -= a[ i ][ k ] * del; 
			}
	}
	for( int i = 1 ; i <= w ; i ++ ) if( fabs( a[ i ][ i ] ) > eps ) a[ i ][ w + 1 ] /= a[ i ][ i ];
}

int n , m , deg[ MAXN + 5 ];
struct node { int v , w; node(){} node( int V , int W ) { v = V , w = W; } };
vector< node > Graph[ MAXN + 5 ];

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 , u , v , w ; i <= m ; i ++ ) {
		scanf("%d %d %d",&u,&v,&w);
		deg[ u ] ++; Graph[ u ].push_back( node( v , w ) );
		if( u != v ) deg[ v ] ++ , Graph[ v ].push_back( node( u , w ) );
	}
	
	w = 2 * n;
	double Ans = 0;
	for( int i = 0 ; i <= LOG ; i ++ ) {
		memset( a , 0 , sizeof( a ) );
		
		a[ 1 ][ w + 1 ] = 1;
		for( int u = 1; u <= n ; u ++ ) {
			a[ u ][ u ] = 1; a[ u + n ][ u + n ] = 1;
			for( node s : Graph[ u ] )
				if( s.v != n ) {
					if( ( s.w >> i ) & 1 ) {
						a[ u ][ s.v ] -= 0;
						a[ u ][ s.v + n ] -= 1.0 / deg[ s.v ];
						a[ u + n ][ s.v ] -= 1.0 / deg[ s.v ];
						a[ u + n ][ s.v + n ] -= 0;
					}
					else {
						a[ u ][ s.v ] -= 1.0 / deg[ s.v ];
						a[ u ][ s.v + n ] -= 0;
						a[ u + n ][ s.v ] -= 0;
						a[ u + n ][ s.v + n ] -= 1.0 / deg[ s.v ];
					}
				}
		}
		
		Gauss();
		Ans += a[ w ][ w + 1 ] * ( 1 << i );
	}
	printf("%.3f\n", Ans );
	return 0;
}